//Given a singly linked list L: L0→L1→…→Ln-1→Ln, 
//reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… 
//
// You may not modify the values in the list's nodes, only nodes itself may be c
//hanged. 
//
// Example 1: 
//
// 
//Given 1->2->3->4, reorder it to 1->4->2->3. 
//
// Example 2: 
//
// 
//Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
// 
// Related Topics 链表


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reorderList(head: ListNode?): Unit {
        if(head == null || head.next == null){
            return
        }
        var slow:ListNode? = head
        var fast:ListNode? = head
        while (fast?.next?.next!= null){
            slow = slow?.next
            fast = fast?.next?.next
        }

        var mid = slow?.next
        slow?.next = null
        //merge list
        mergeList(head, reverseList(mid)!!)
    }

    fun mergeList(list1:ListNode,list2:ListNode){
        var head:ListNode? = list1
        var p1:ListNode? = list1.next
        var p2:ListNode? = list2
        while (p2 != null && p1 != null) {
            head?.next = p2
            head = p2
            p2= p2?.next
            head?.next = p1
            head = p1
            p1 = p1?.next
        }
        if (p1 != null) {
            head?.next = p1
        }else if(p2 !=null){
            head?.next = p2
        }
    }

    fun reverseList(head: ListNode?):ListNode?{
        var current = head
        var pre:ListNode ?= null
        while (current != null) {
            val next = current.next
            current.next = pre
            pre = current
            current = next
        }
        return pre

    }
}
//leetcode submit region end(Prohibit modification and deletion)
